package javase.LeetCode;

import java.util.ArrayList;
import java.util.List;

public class Test1 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.generateParenthesis(3));
    }
}
class Solution {
    public List<String> generateParenthesis(int n) {
        StringBuilder sb = new StringBuilder();
        List<String> res = new ArrayList<>();
        dfs(sb,res,0,0,n);
        return res;
    }
    private void dfs(StringBuilder sb,List<String> res,int right,int left,int n){
        if(right==n&&left==n){
            res.add(sb.toString());
            return ;
        }
        if(right<n){
            sb.append("(");
            dfs(sb,res,right+1,left,n);
            sb.deleteCharAt(sb.length()-1);
        }
        if(left<right){
            sb.append(")");
            dfs(sb,res,right,left+1,n);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
